package puzzle.projecteuler.p300;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

/**
 * 注意结果四舍五入。
 * @author wong tong
 *
 */
public class Problem205C {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int[] dices0 = {9, 4};
		int[] dices1 = {6, 6};
		
		Map<Integer, Integer> A = dice(dices0[0],dices0[1]);
		Map<Integer, Integer> B = dice(dices1[0],dices1[1]);
		BigInteger p = BigInteger.ZERO;
		for (Integer a: A.keySet()) {
			for (Integer b: B.keySet()) {
				if (a > b) {
					BigInteger x = BigInteger.valueOf(A.get(a)*B.get(b));
					p = p.add(x);
				}
			}
		}
		BigInteger q1 = BigInteger.valueOf(dices0[1]).pow(dices0[0]);
		BigInteger q2 = BigInteger.valueOf(dices1[1]).pow(dices1[0]);
		BigInteger q = q1.multiply(q2);
		System.out.println(p.toString() + "/" + q.toString() + " = " + p.doubleValue()/q.doubleValue());
	}

	/**
	 * 返回Map, Key 表示点数，Value 表示可能出现的次数
	 * @param n number of dice
	 * @param m each dice has numbers from 1 to m
	 * @return
	 */
	private static Map<Integer, Integer> dice(int n, int m) {
		
		if (n == 1) {
			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
			for (int i = 1; i <= m; i ++) {
				map.put(i, 1);
			}
			return map;
		} else {
			Map<Integer, Integer> t = dice(n-1, m);
			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
			for (int i = 1; i <= m; i ++) {
				for (Integer j: t.keySet()) {
					Integer k = i + j;
					Integer v = (map.get(k) == null)?t.get(j):map.get(k)+t.get(j);
					map.put(k, v);
				}
			}
			return map;
		}
	}
}
